package com.lw.leetcode.node;

/**
 * 623. 在二叉树中增加一行
 *
 * @Author liw
 * @Date 2021/5/12 9:42
 * @Version 1.0
 */
public class AddOneRow {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth < 1) {
            return root;
        }
        if (depth == 1) {
            TreeNode node = new TreeNode(val);
            node.left = root;
            return node;
        }
        find(root, val, depth, 2);
        return root;
    }

    public void find(TreeNode root, int val, int depth, int n) {
        if (root == null) {
            return;
        }
        if (n == depth) {
            TreeNode l = new TreeNode(val);
            l.left = root.left;
            root.left = l;
            TreeNode r = new TreeNode(val);
            r.right = root.right;
            root.right = r;
            return;
        }
        n++;
        find(root.left, val, depth, n);
        find(root.right, val, depth, n);
    }
}
